A wide variety of pattern recognition systems are known in the art. Each such system optically receives data depicting a pattern to be recognized, and performs certain tasks on this pattern in order to compare it to known patterns in order to "recognize" the input pattern. A basic flow chart depicting a pattern recognition system is shown in FIG. 1. The input pattern is the pattern which is desired to be recognized. Digitizer 12 converts input pattern 11 to a series of bytes for storage in system memory 13. These bytes are typically binary in nature, reflecting the fact that input pattern 11 is basically a black and white figure. Digitizers are well known in the art and typically are used in such devices as facsimile machines, electronic duplicating machines (as opposed to optical photocopy machines) and optical character recognition systems of the prior art. Memory 13 can comprise any suitable memory device, including random access memories of well-known design. Segmentation 14 serves to divide the image data stored in memory 13 into individual characters. Such segmentation is known in the prior art, and is described, for example, in Digital Picture Processing, Second Edition, Volume 2, Azriel Rosenfeld and Avinash C. Kak, Academic Press, 1982, specifically, Chapter 10 entitled "Segmentation".
Feature extraction 15 serves to transform each piece of data (i.e., each character) received from segmentation 14 in order to transform that data into a standard predefined form for use by identification means 16, which in turn identifies each character as one of a known set of characters. Output means 17 serves to provide data output (typically ASCII, or the like) to external circuitry (not shown), as desired. Identification means 16 can be any one of a number of prior art identification means typically used in pattern recognition systems, including, more specifically, optical character recognition systems. One such identification means suitable for use in accordance with the teachings of this invention is described in U.S. Pat. No. 4,259,661, issued Mar. 31, 1981 to Todd, entitled "Apparatus and Method for Recognizing a Pattern". Identification means 16 is also described in Syntactic Pattern Recognition and Applications, K. S. Fu, Prentice Hall, Inc., 1982, specifically, Section 1.6, and Appendices A and B.
Inasmuch as this invention pertains to a method and structure for use as identification means 16 for use in an optical character system, this specification, including the description of prior art herein, is directed to identification mean 16, although it is to be understood that the teachings of this invention are equally applicable for use in pattern recognition systems recognizing patterns other than characters, or indeed even to systems used to recognize any information capable of being represented mathematically.
Prior art identification techniques include matrix overlay techniques, in which a feature vector containing pixels defining each bit of the unknown character is compared, for example, by an exclusive OR operation, with a feature vector defining the pixels in a known reference character. This is performed in sequence for a series of known reference characters, and the result of the exclusive OR operations which yields the minimum number of mismatched pixels between the unknown character and a reference character causes the unknown character to be recognized as that reference character.
Another prior art classification technique is a so-called "decision tree" technique. In this technique, a series of relevant questions is posed and answered by the input data defining the input pattern to be recognized. The results of the various answers to these questions results in a decision tree which, after a number of branches, results in the identification of the input pattern.